Pseudo-noise ("PN") codes are finding increasing application, for example in the area of wireless telephony. In code division multiple access telephony, for example, a digitized data stream is encoded using PN codes, to "spread" the spectrum of the signal transmitting the data. The digitized data stream is decoded using the same PN code used to encode it at the transmitter.
By illustration, FIG. 1 shows a block diagram of a portion of a code division multiple access ("CDMA") receiver unit. Specifically, FIG. 1 shows the functional blocks of a CDMA digital baseband functional unit 10 useful in understanding an application of the present invention. The blocks are implemented primarily in software running on a digital signal processor ("DSP").
Thus, there is shown an Energy Estimator unit 18, a Searcher 20, and a plurality of "Fingers" 22, each of which receives the two-wide input line 12 as an input. The outputs of the Energy Estimator unit 18, Searcher 20 and "Fingers" 22, are provided to other functional units represented collectively by block 24, such as, for reception, rate detection, symbol alignment, Viterbi decoding, etc., and, for transmission, encoding, interleaving, etc. Voice signals are provided on line 14 to block 24. Signals from Estimator unit 18 are provided on line 26 to block 24. Signals from Searcher 20 are provided on line 28 to block 24. Signals from Fingers 22 are provided on lines 30 to block 24. A Transmit Processing unit 32 receives encoded data signals on line 34. The output of Transmit Processing unit 32 is provided on line 16.
A PN Code Generator unit 36 provides PN code signals on line 38 to Fingers 22, and on lines 40 to Transmit Processing unit 32. The PN Code Generator unit 36 receives control signals on lines 42 from block 24, and it receives clock signals from a Clock Generator 44 on lines 46. Clock Generator 44 also provides clock signals on lines 48 for various other clocked functions in Functional unit 10.
As a general matter, in operation, functional unit 10 receives I and Q encoded data streams on two-wide input lines 12, provided from an RF front end unit (not shown), and performs various functions associated with CDMA reception, such as signal acquisition, rate determination, Viterbi decoding, digital-to-analog conversion, and the like. The I,Q encoded data is provided in the form of binary encoded sample values of the analog RF signal received at the RF front end, since the implementation of the functional unit 10 is in a software process executed using a DSP, which requires such binary encoded sample form for the data.
Functional unit 10 also receives voice signals on line 14, performs various transmission functions, such as analog-to-digital conversion and encoding, and provides I,Q coded, spread-spectrum signals on two-wide output line 16 for modulation and transmission by the RF front end unit.
Specifically, the binary encoded sample values, of I,Q coded data, on line 12 are provided to Energy Estimator 18, which performs various operations on the data to estimate the average envelope strength of the received signal, and provides the result on line 26 for further processing. The binary encoded sample values, of I,Q coded data, on line 12 are also provided to Searcher 20, which performs various operations on the data to identify received signals for allocation to one of the Fingers 22, the data for such selection being provided to block 24 on line 28. Finally, the binary encoded sample values, of I,Q coded data, are provided on line 12 to Fingers 22 where some binary encoded values are selected and used in a decoding operation using a PN code provided on line 38 by PN Code Generator 36 to determine whether the PN Code Generator code signal is at the proper timing to decode the signal on line 12.
The PN Code Generator 36 also provides PN code signals, on lines 40, to the Transmit Processing Unit 32, which uses such PN code signals to spread-spectrum encode the digitized voice data, which may be Walsh encoded, e.g., provided on line 34 from block 24. The spread-spectrum signal resulting from this process is provided on output line 16. The PN Code Generator 36 also includes a Mask Generator subunit 37, which generates a mask for use in immediate shifts of the PN Code Generator 36 output, as is discussed in detail hereinbelow.
All of the foregoing, in general, is well known in the spread-spectrum communications art. Further details of the various functional units of such a CDMA digital baseband functional unit 10, other than that of the PN code generator 36, are, therefore, not pertinent to an understanding of the present invention, and so, in the interest of clarity and brevity are not described in detail herein. The PN code generator 36, however, is pertinent, and is described further hereinbelow.
First, turning to a general discussion of PN codes, PN codes are generated by pseudo-noise sequence generators ("PNSGs"). One familiar apparatus used in PNSGs is a device known as a linear feedback shift register ("LFSR"). However, PNSGs are not limited to LFSRs. An PNSG is typically composed of a series of N stages, each stage including a memory element or memory step (depending on whether the PNSG is hardware or software), whose inputs are a linear combination (modulo 2) of the output memory element or step and previous memory element or step when viewed from a left-to-right perspective. The individual ones and zeros ("bits") of the output sequence of a PNSG, i.e., of a PN code, are sometimes referred to as "chips." A specific example of a PNSG 1 for N=4 is shown in FIG. 2. It will be understood that the PNSG 1 may be implemented in hardware, for example as an LFSR, or it may be implemented in software, for example for execution on a DSP, in which case FIG. 2 represents a structure for the logical flow of the method so implemented. Discussion below assumes software implementation.
In FIG. 2 can be seen the four memory steps 50, 52, 54, 56, as well as an addition step 58 disposed between memory steps 54 and 56. The output of memory step 50 is provided to the input of memory step 52, the output of memory step 52 is provided to the input of memory step 54, while the output of memory step 54 is provided to one input of addition step 58. The output of addition step 58 is provided to the input of memory step 56, with the output of the PNSG being the output 60 of memory step 56. A feedback path 60' is also provided from the output 60 of memory step 56 to the input of memory step 50 and to the other input of addition step 58.
The operation of the PNSG 1 shown in FIG. 2 can be described by either a state diagram or a table. The "state" of the PNSG 1 is the value of the bits stored in the memory steps before a given iteration. Thus, for PNSG 1, the state before iteration "n" may be expressed as S.sub.n =mnop, where m, n, o and p are the value of the bits stored in memory steps 50, 52, 54, 56, respectively. If the memory steps 50, 52, 54, 56, of PNSG 1 are initialized with the state S.sub.0 =0001, the output and subsequent states of the PNSG are as shown in Table 1:
TABLE 1 ______________________________________ Clock Cycle or Iteration State Output ______________________________________ 0 0001 1 1 1001 1 2 1101 1 3 1111 1 4 1110 0 5 0111 1 6 1010 0 7 0101 1 8 1011 1 9 1100 0 10 0110 0 11 0011 1 12 1000 0 13 0100 0 14 0010 0 15 0001 1 ______________________________________
With respect to Table 1, note that after the 15th iteration the state of the PNSG reaches that of the initial or 0th iteration. In fact, the output and state sequences of the PNSG repeat with a period of 15. For the case of N=4, this represents the maximum possible period since the all zeros state never occurs. Thus, in general, a PNSG is capable of generating a sequence of period (or, length) 2.sup.N -1, where N is the number of stages. Not all PNSG configurations generate a sequence with the largest possible period, but those that do are said to generate a maximal length sequence or m-sequence for short. For the purposes of the present invention, PNSGs that generate m-sequences are of primary interest and hence discussion herein is focused on PNSGs having this property.
Now, it is often desirable to generate a delayed version of a PN code relative to some master, or reference, sequence. While it is possible to use a simple delay line to accomplish this, it is frequently necessary to generate very long delays that cause this approach to become impractical.
A superior technique for generating a delayed PN code exploits the shift-and-add property of m-sequences. This property means that when a shifted or delayed version of a PN code is added to itself, the resulting code is merely a delayed version of the original. To better understand this, consider the following sequence generated by the PNSG 1 of FIG. 2:
. . 111101011001000 . . . . PA0 . . 011110101100100 . . . . PA0 . . 100011110101100 . . . ,
If this sequence is shifted or delayed by one chip, the result is
Adding these two sequences together using modulo 2 arithmetic yields
which is merely the original PN sequence delayed by 4 chips. While other specific delays can be generated in this fashion, a more efficient and sophisticated method is described next.
Referring to the State column in Table 1, notice that the sequence associated with a particular stage represents a delayed version of the PNSG output. E.g., the sequence corresponding to the least significant bit of the state vector is identical to the output; the sequence corresponding to the most significant bit is the output delayed by one chip, etc. Thus according to the shift-and add property of m-sequences, another PN code having a specific delay relative to the original sequence can be generated by adding together one or more outputs of the four stages.
FIG. 3 shows a PN sequence generator having a PNSG 1, similar to the arrangement of FIG. 2, but also having an associated PN shifter 62. As in FIG. 1, four memory steps 50, 52, 54, 56, an addition step 58, an output 60 and a feedback path 60' are provided, interconnected as in FIG. 2. Also provided, however, is shifter 62. The shifter 62 is comprised of an additional four memory steps 64, 66, 68, and 70. These receive a PN shift-and-add mask value over an input 72. The output of memory step 64 is provided to one input of a first multiplier 74. The other input of multiplier 74 is the output of memory step 50. The output of memory step 66 is provided to one input of a second multiplier 76. The other input of multiplier 76 is the output of memory step 52. The output of memory step 68 is provided to one input of a third multiplier 78. The other input of multiplier 78 is the output of memory step 54. The output of memory step 70 is provided to one input of a fourth multiplier 80. The other input of multiplier 80 is the output of memory step 56.
The output of multiplier 74 is provided to one input of a second addition step 82. The output of multiplier 76 is provided to the second input of addition step 82, while the output of addition step 82 is provided to one input of a third addition step 84. The output of multiplier 78 is provided to the second input of addition step 84, while the output of addition step 84 is provided to one input of a fourth addition step 86. The output of multiplier 80 is provided to the second input of addition step 86. The output 88 of addition step 86 provides the same sequence as the output 60 of the PNSG 1, but delayed by an amount determined by the value of the shift-and-add mask stored in memory steps 64, 66, 68, and 70.
Thus, by forming the inner product of a shift-and-add mask, hereinafter simply referred to as a "mask," stored in the memory steps 64, 66, 68, 70, with the states of the PNSG, stored in the memory steps 50, 52, 54, 56, as shown in FIG. 2, a second sequence can be generated with a known delay relative to the PNSG output. This second sequence is, as mentioned above, provided at the output 88 of addition step 86.
However, a problem that exists in the practical application of the use of a mask for accomplishing rapid shifts of PN sequences is in the time it takes to generate the mask itself. For example, PN sequence generators are currently being used in code division multiple access ("CDMA") cellular telephone applications. Data rates in such applications are high. Rapid shifts in the PN sequences generated in such applications must also be rapid. Therefore, there is a need for a method and apparatus for generating a mask rapidly, yet controllably and accurately.